A Bloom Filter (BF) is a probabilistic data structure that can represent set membership in an approximate manner. A Bloom filter responds to membership queries without false negatives, but may provide a false positive at a bounded rate. That is, a query to the filter on whether x is in the set is always correct if item x was inserted into the set S, but may err when the item x in not in S (false positive).
A Counting Bloom filter (CBF) is a data structure similar to a Bloom filter, but instead of providing a single bit in each position of the filter, a counter is provided. Using a counter enables not only adding items to the filter, but also removing items therefrom, without having to re-calculate the filter altogether and without potentially creating false negative in view of a deletion.